package 牛客;
/*
 *@Author: helen
 *@Date:   2021/4/27 10:46
 *@Description:
 */

import java.util.ArrayList;
import java.util.HashMap;

public class 找出数组中重复的数字 {
    //题目描述：在一个长度是n的数组里，而且所有数字都在0~n之间，找出重复的数字


    //方法1：时间复杂度O(n),但需要消耗一个HashMap的空间，可以把所有的重复数字都找出来
    public ArrayList<Integer> FindRepeatNum(int[] arr){
        ArrayList<Integer> list = new ArrayList<>();
        if(arr == null)
            return list;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i]))
                list.add(arr[i]);
            else
                map.put(arr[i], i);
        }
        return list;

    }

    //方法2：时间复杂度O(n), 空间复杂度O(1)
            //给第i个位置找到元素i
    public ArrayList<Integer> FindRepeatNum02(int[] arr){
        ArrayList<Integer> list = new ArrayList<>();
        if(arr == null)
            return list;
        for (int i = 0; i < arr.length; i++) {
            while (arr[i] != i) {      //每个元素最多只要交换2次即可找到它自己的位置
                if (arr[i] == arr[arr[i]]) {
                    if(!list.contains(arr[i]))  //判断该重复元素是否已经加入过list
                        list.add(arr[i]);
                    break;
                }
                else {
                    int temp = arr[i];
                    arr[i] = arr[temp];
                    arr[temp] = temp;
                }
            }
        }
        return list;
    }



    //题目描述：在一个长度是n+1的数组里，而且所有数字都在1~n之间，找出重复的数
    //方法3：要求不能修改原来数据：时间复杂度O(n),空间复杂度O(n)
    public ArrayList<Integer> FindRepeatNum03(int[] arr){
        ArrayList<Integer> list = new ArrayList<>();
        if(arr == null)
            return list;
        int[] m = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            if(m[arr[i]] == arr[i]) {
                if(!list.contains(arr[i]))
                    list.add(arr[i]);
                continue;
            }
            m[arr[i]] = arr[i];
        }
        return list;
    }

    //方法4：要求不能修改原来数据：时间复杂度O(n log n),空间复杂度O(1)  只能找出任意一个重复的数字
    public int FindRepeatNum04(int[] arr) {
        if (arr == null)
            return -1;
        int start = 1;
        int end = arr.length - 1;
        while (end >= start){
            int middle = ((end - start)>> 1) + start;
            int count = countRange(arr, start, middle);
            if(end == start){
                if(count > 1)
                    return start;
                else break;
            }
            if(count > (middle - start + 1))
                end = middle;
            else start = middle + 1;
        }
        return -1;
    }

    public int countRange(int[] arr, int start, int end){
        int count = 0;
        if(arr == null)
            return -1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] >= start && arr[i] <= end)
                count++;
        }
        return count;
    }

    public static void main(String[] args) {
        找出数组中重复的数字 obj = new 找出数组中重复的数字();
        int[] arr01 = {2,3,1,0,2,5,3};
        int[] arr02 = {2,1,3,0,2,3,3};
        int[] arr03 = {2,3,5,4,3,2,6,7};
        int[] arr04 = {2,3,5,4,2,2,6,7};
        System.out.println(obj.FindRepeatNum(arr01));
        System.out.println(obj.FindRepeatNum02(arr02));
        System.out.println(obj.FindRepeatNum03(arr03));
        System.out.println(obj.FindRepeatNum04(arr04));
    }
}
